package main

import "fmt"
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
//中序遍历 左 根 右
func inorder(root *TreeNode) (res []int){
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode){
		if node == nil{
			return
		}
		inorder(node.Left)
		res = append(res,node.Val)
		inorder(node.Right)
	}
	inorder(root)
	return
}

//先序遍历 根 左 右
func preorder(root *TreeNode) (res []int){
	var preorder func(node *TreeNode)
	preorder = func(node *TreeNode){
		if node == nil{
			return
		}
		res = append(res, node.Val)
		preorder(node.Left)
		preorder(node.Right)
	}
	preorder(root)
	return

}

//后序遍历 左 右 根
func postorder(root *TreeNode) (res []int){
	var postorder func(node *TreeNode)
	postorder = func(node *TreeNode){
		if node == nil{
			return
		}
		postorder(node.Left)
		postorder(node.Right)
		res = append(res, node.Val)
	}
	postorder(root)
	return
}
//层次遍历 用队列实现
func levelorder(root *TreeNode) [][]int{
	var res [][]int
	queue := []*TreeNode{root}
	if root == nil{
		return res
	}
	for len(queue) > 0{
		size := len(queue)
		//定义一个切片来存储出队列的值
		cur := []int{}
		for i:=0;i<size;i++{
			//临时变量存储队列中的元素
			node := queue[i]
			//将队列中元素的值加入到这个切片里
			cur = append(cur, node.Val)
			//寻找队列里元素的左右孩子，如果不为空就入队
			if node.Left != nil{
				queue = append(queue, node.Left)
			}
			if node.Right != nil{
				queue = append(queue, node.Right)
			}
		}
		//遍历队列结束后，把上一层对应的元素出队
		queue = queue[size:]
		//把所有结果加入到最后的结果上
		res = append(res, cur)
	}
	return res
}

func main() {
	root := &TreeNode{Val: 3}
	root.Right = &TreeNode{Val: 20}
	root.Right.Left = &TreeNode{Val: 15}
	root.Right.Right=&TreeNode{Val: 7}
	root.Left = &TreeNode{Val: 9}
	fmt.Println("中序遍历的结果为:", inorder(root))
	fmt.Println("先序遍历的结果为:",preorder(root))
	fmt.Println("后序遍历的结果为:",postorder(root))
	fmt.Println("层次遍历的结果为:", levelorder(root))
}